#include <iostate>
#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        if(size == 0)
            return 0;

        vector<int> tmp(size, 0);
        for(int i = 0; i < size; i++)
            tmp[i] = gas[i] - cost[i];
        
        int res = 0;
        for(int i = 0; i < size; i++){
            if(tmp[i] < 0)
                continue;
            res = tmp[i];
            for(int j = (i + 1)%size; j != i; j = (j+1)%size){
                res += tmp[j];
                if(res < 0){
                    break;
                }
            }
            if(res >= 0)
                return i;
        }

        return -1;
    }
};


class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        int start = -1, total = 0, sum = 0;
        for(int i = 0; i < size; i++){
            sum = gas[i] - cost[i] + sum;
            total = gas[i] - cost[i] + total;
            if( sum < 0 ){
                sum = 0;
                start = i;
            }

        }

        return total < 0? -1:start+1;
            
    }
    
};
